package labuladong.动态规划;

import java.util.HashMap;

/**
 * 编辑距离
 * https://mp.weixin.qq.com/s/uWzSvWWI-bWAV3UANBtyOw
 */
public class Demo04 {
    public static void main(String[] args) {
        String s1="horse";
        String s2 = "ros";
        System.out.println(minDistance2(s1, s2));
    }

    /**
     * 不含过程
     * @param s1
     * @param s2
     * @return
     */
    public static int minDistance(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++){
            dp[i][0] = i;
        }
        for(int j=1; j<=n; j++){
            dp[0][j] = j;
        }
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(s1.charAt(i-1) == s2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+1);
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 包含过程。但是报错？？？
     * @param s1
     * @param s2
     * @return
     */
    public static int minDistance2(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        Node[][] dp = new Node[m+1][n+1];

        for(int i=1; i<=m; i++){
            dp[i][0].val = i;
        }

        for(int j=1; j<=n; j++){
            dp[0][j].val = j;
        }

        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j].val = dp[i-1][j-1].val;
                    dp[i][j].choice = 0;
                }else{
                    dp[i][j].val = Math.min(Math.min(dp[i-1][j].val+1, dp[i][j-1].val+1), dp[i-1][j-1].val+1);
                    if (dp[i][j].val == dp[i - 1][j].val + 1) {
                        dp[i][j].choice = 2;
                    } else if(dp[i][j].val == dp[i][j-1].val+1) {
                        dp[i][j].choice = 1;
                    }else {
                        dp[i][j].choice = 3;
                    }
                }
            }
        }
        for(int i=1; i<=m; i++){
            for(int j=1; i<=n; j++){
                System.out.print(dp[i][j].choice+" ");
            }
            System.out.println();
        }
        return dp[m][n].val;
    }

     class Node {
        int val;
        int choice;
        // 0 代表什么都不做
        // 1 代表插入
        // 2 代表删除
        // 3 代表替换
    }
}
